package com.itheima.algorithm.binarysearch;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertionSort {

    public static void sort(int[] a) {
        insertion2(a,1);
    }

    /**
     * @param a
     * @param low 未排序区域下边界
     */
    private static void insertion1(int[] a, int low) {
        if (a.length == low) {
            return;
        }
        int temp = a[low];

        //已排序区域指针
        int i = low - 1;

        while (i >= 0 && a[i] > temp) { // 没有找到插入位置
            // 空出插入位置
            a[i+1] = a[i];
            i--;
        }
        //找到插入位置,temp赋值给i+1位置
        a[i + 1] = temp;
        insertion1(a, low + 1);
    }

    /**
     * 第二周解法 时间复杂度相同，但是while循环内比第一次赋值占用的空间更多
     * @param a
     * @param low
     */
    private static void insertion2(int[] a, int low) {
        if (a.length == low) {
            return;
        }

        //已排序区域指针
        int i = low - 1;

        while (i >= 0 && a[i] > a[i+1]) { // 没有找到插入位置
            // 空出插入位置
            int t = a[i];
            a[i] = a[i+1];
            a[i+1] = t;

            i--;
        }
        insertion1(a, low + 1);
    }

    public static void main(String[] args) {
        int [] a = {3,1,2,4,5};
        sort(a);
        System.out.println(Arrays.toString(a));
    }

}
